#ifndef LISTAENCADEADA_H_
#define LISTAENCADEADA_H_

//Lista Encadeada Nao Ordenada
//Elementos inseridos no fim

#include <iostream>

template<class TIPO_DADO, class TIPO_CHAVE>
class ListaEncadeada
{
public:
	
	ListaEncadeada();
	~ListaEncadeada();
	
	/*Auxiliares*/
	bool isEmpty();
	bool itsTheEnd();
	int getNumElem();
	void zeraPercorrendo();
	
	/*Estruturais*/
	bool inserir(TIPO_DADO, TIPO_CHAVE);
	bool rancarFora(TIPO_DADO*, TIPO_CHAVE);	
	bool excluir(TIPO_CHAVE);
	
	/*Percurso*/
	TIPO_DADO* retornaEsteEAvanca();
	bool get(TIPO_DADO*, TIPO_CHAVE);
	bool getPrimeiro(TIPO_DADO*);
	bool getUltimo(TIPO_DADO*);
	bool getProximo(TIPO_DADO*, TIPO_CHAVE);
	
	
private:

	typedef struct Noh
		{
			TIPO_DADO dado;
			TIPO_CHAVE chave;
		
			Noh* MyBack;
		};
	
	
	Noh* inicio;
	Noh* fim;
	Noh* mpPercorrendo;
	
	int numElem;
	
	void inicializar();
	bool buscar(TIPO_CHAVE, Noh**);
	
};

// Como a Class usa "template",  a implementação deve ser feita no mesmo arquivo

//CONSTRUTOR / DESTRUTOR
template<class TIPO_DADO, class TIPO_CHAVE>
ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::ListaEncadeada()
{	
	this->inicializar();
}

template<class TIPO_DADO, class TIPO_CHAVE>
ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::~ListaEncadeada()
{
	if (! this->isEmpty())
	{
		Noh *deletar;
		Noh *percorre = this->inicio;
		do
		{
			if ( percorre->MyBack == NULL )
			{
				delete percorre;
				percorre = NULL;
				return;
			}
			else
				{
					deletar = percorre;
					percorre = percorre->MyBack;
					delete deletar;
				}
		}while(1);
	}		
}

// METODOS AUXILIARES
template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::isEmpty()
{
	return (this->inicio == NULL) ? true : false;
}

template<class TIPO_DADO, class TIPO_CHAVE>
void ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::inicializar()
{
	this->inicio = NULL;
	this->fim = NULL;
	this->numElem = 0;
	this->mpPercorrendo = NULL;
}


template<class TIPO_DADO, class TIPO_CHAVE>
int ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::getNumElem()
{
	return this->numElem;
}

//METODOS ESTRUTURAIS
template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::inserir(TIPO_DADO vDadoIns, TIPO_CHAVE vChaveIns)
{
	Noh *novoNoh = new struct Noh;
	if (novoNoh == NULL)
	{
		return false;
	}
	
	novoNoh->MyBack = NULL;
	novoNoh->dado = vDadoIns;
	novoNoh->chave = vChaveIns;
	
	if(isEmpty())
	{
		this->inicio = novoNoh;
		this->fim = novoNoh;
		this->mpPercorrendo = novoNoh;
		this->numElem++;
		return true;
	}
	else
		{
			this->fim->MyBack = novoNoh;
			this->fim = novoNoh;
			
			this->numElem++;
			return true;
		}
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::rancarFora(TIPO_DADO *pRetorno, TIPO_CHAVE vChaveRanca)
{
	if(this->isEmpty())
	{
		return false;
	}
	if(this->inicio->chave == vChaveRanca)
	{
		Noh* pTempNoh = this->inicio;
		if (this->inicio == this->fim)
		{
			this->inicio = NULL;
			this->fim = NULL;
		}else
			{
				this->inicio = this->inicio->MyBack;
			}		
		*pRetorno = pTempNoh->dado;	
		delete pTempNoh;	
		--this->numElem;
		return true;
	}
	else
		{
			Noh* percorre;
			percorre = this->inicio;
			if ( percorre->MyBack == NULL)
			{
				return false;
			}
			while (percorre != NULL )
			{
				if ( percorre->MyBack->chave == vChaveRanca )
				{
					Noh* rancando = percorre->MyBack;
					percorre->MyBack = percorre->MyBack->MyBack;
					
					if (rancando->MyBack == NULL)
					{
						this->fim = percorre;
					}					
					*pRetorno = rancando->dado;
					delete rancando;
					--this->numElem;					
					return true;
				}
				percorre = percorre->MyBack;				
			}
			return false;	
		}
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::excluir(TIPO_CHAVE vChaveRem)
{
	if(this->isEmpty())
	{
		return false;
	}
	if(this->inicio->chave == vChaveRem)
	{
		Noh* pTempNoh = this->inicio;
		if (this->inicio == this->fim)
		{
			this->inicio = NULL;
			this->fim = NULL;
		}else
			{
				this->inicio = this->inicio->MyBack;
			}
		
		delete pTempNoh;
		
		--this->numElem;
		return true;
	}
	else
		{
			Noh* percorre;
			percorre = this->inicio;
			if ( percorre->MyBack == NULL)
			{
				return false;
			}
			while (percorre != NULL )
			{
				if ( percorre->MyBack->chave == vChaveRem )
				{
					Noh* deleting = percorre->MyBack;
					percorre->MyBack = percorre->MyBack->MyBack;
					
					if (deleting->MyBack == NULL)
					{
						this->fim = percorre;
					}					
					delete deleting;
					--this->numElem;					
					return true;
				}
				percorre = percorre->MyBack;				
			}
			return false;
		}							
}


//METODOS DE PERCURSO
template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::buscar(TIPO_CHAVE buscandoChave, Noh** pRetorno)
{
	if(this->isEmpty())
	{
		return false;
	}
	
	Noh* pPercorre = this->inicio;
	
	while ( pPercorre != NULL )
	{
		if ( pPercorre->chave == buscandoChave )
		{
			*pRetorno =  pPercorre;
			return true;			
		}else
			pPercorre = pPercorre->MyBack;
	}
	return false;	
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::get(TIPO_DADO* pGetRetorno, TIPO_CHAVE vGetChave)
{
	Noh* seAchouTaqui;
	if (this->buscar(vGetChave, &seAchouTaqui))
	{
		*pGetRetorno = seAchouTaqui->dado;
		return true;
	}else
	{
		return false;
	}	
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::getPrimeiro(TIPO_DADO* pRetorno)
{
	if (! this->isEmpty())  
	{
		*pRetorno = this->inicio->dado;
		return true;
	}
	else
	{
		return false;
	}	
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::getUltimo(TIPO_DADO* pRetorno)
{
	if (! this->isEmpty())
	{
		*pRetorno = this->fim->dado;
		return true;
	}
	else
	{
		return false;
	}
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::getProximo(TIPO_DADO* pNextRetorno, TIPO_CHAVE vKey)
{
	Noh* seAchouTaqui;
	if (this->buscar(vKey, &seAchouTaqui))
	{
		if ( seAchouTaqui->MyBack != NULL)
		{
			*pNextRetorno = seAchouTaqui->MyBack->dado;
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		return false;
	}		
}

template<class TIPO_DADO, class TIPO_CHAVE>
bool ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::itsTheEnd()
{
	if(mpPercorrendo == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

template<class TIPO_DADO, class TIPO_CHAVE>
TIPO_DADO* ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::retornaEsteEAvanca()
{
	TIPO_DADO* pAuxiliar;
	pAuxiliar = &this->mpPercorrendo->dado;
	this->mpPercorrendo = this->mpPercorrendo->MyBack;
	return pAuxiliar;
}

template<class TIPO_DADO, class TIPO_CHAVE>
void ListaEncadeada<TIPO_DADO, TIPO_CHAVE>::zeraPercorrendo()
{
	mpPercorrendo = inicio;
}

#endif /*LISTAENCADEADA_H_*/

